<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Implementations of Domains and Constraints
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial047.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial046.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial049.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc96">7.2</A>&nbsp;&nbsp;Implementations of Domains and Constraints</H2><UL>
<LI><A HREF="tutorial048.html#toc50">Suspended Goals: <EM>suspend</EM></A>
<LI><A HREF="tutorial048.html#toc51">Interval Solver: <EM>ic</EM></A>
<LI><A HREF="tutorial048.html#toc52">Global Constraints: <EM>ic_global</EM></A>
<LI><A HREF="tutorial048.html#toc53">Scheduling Constraints: <EM>ic_cumulative, ic_edge_finder</EM></A>
<LI><A HREF="tutorial048.html#toc54">Finite Integer Sets: <EM>ic_sets</EM></A>
<LI><A HREF="tutorial048.html#toc55">Linear Constraints: <EM>eplex</EM></A>
<LI><A HREF="tutorial048.html#toc56">Constraints over symbols: <EM>ic_symbolic</EM></A>
</UL>


<A NAME="toc50"></A>
<H3 CLASS="subsection"><A NAME="htoc97">7.2.1</A>&nbsp;&nbsp;Suspended Goals: <EM>suspend</EM></H3>
<A NAME="@default167"></A>
<A NAME="shortsecsuspend"></A>
The constraint solvers of  ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> are all implemented using suspended
goals.
The simplest implementation of any constraint is to suspend it
until all its variables are sufficiently instantiated, and then test it.<BR>
<BR>
The <EM>suspend</EM> solver implements this behaviour for all
the mathematical constraints of  ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>,
&gt;=, &gt;, =:=, =\=, =&lt; and &lt;.<BR>
<BR>
<A NAME="toc51"></A>
<H3 CLASS="subsection"><A NAME="htoc98">7.2.2</A>&nbsp;&nbsp;Interval Solver: <EM>ic</EM></H3>
<A NAME="@default168"></A>
<A NAME="shortsecic"></A>
The standard constraint solver offered by most constraint programming
systems is the <EM>finite domain</EM> solver, which applies constraint
propagation techniques developed in the AI community [<A HREF="tutorial133.html#VanHentenryck"><CITE>27</CITE></A>]. 
 ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> supports finite domain constraints via the <EM>ic</EM>
library<SUP><A NAME="text1" HREF="tutorial046.html#note1">1</A></SUP>.
The library implements finite domains of integers, together with a basic
set of constraints.<BR>
<BR>
In addition, <EM>ic</EM> also allows <EM>continuous domains</EM>
(in the form of numeric intervals), and constraints
(equations and inequations) between expressions involving
variables with continuous domains.
These expressions can contain non-linear functions such as <I>sin</I> and built-in
constants such as <I>pi</I>.
Integrality is treated as a constraint, and it is possible to mix
continuous and integral variables in the same constraint.
Specialised search techniques 
(<EM>splitting</EM> [<A HREF="tutorial133.html#VanHentenryck:95"><CITE>26</CITE></A>] and <EM>squashing</EM> 
[<A HREF="tutorial133.html#lhomme96boosting"><CITE>15</CITE></A>]) support
the solving of problems with continuous variables.<BR>
<BR>
Most constraints are also available in reified form, providing
a convenient way of combining several primitive constraints.<BR>
<BR>
Note that the <EM>ic</EM> library itself implements only a standard,
basic set of arithmetic constraints. 
Many more finite domain
constraints can be defined, which have uses in specific applications.
The behaviour of these constraints is to prune the finite domains of
their variables, in just the same way as the standard constraints.
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> offers several further libraries which implement such
constraints using the underlying domain of the <EM>ic</EM> library. <BR>
<BR>
<A NAME="toc52"></A>
<H3 CLASS="subsection"><A NAME="htoc99">7.2.3</A>&nbsp;&nbsp;Global Constraints: <EM>ic_global</EM></H3>
<A NAME="@default169"></A>
<A NAME="shortsecglobal"></A>
<A NAME="secglobalcstr"></A>
One such library is <EM>ic_global</EM>.
It supports a variety of constraints, each of which takes as an argument
a list of finite domain variables, of unspecified length.
Such constraints are called &#8220;global&#8221; constraints [<A HREF="tutorial133.html#beldiceanu"><CITE>2</CITE></A>].
Examples of such constraints, available from the <EM>ic_global</EM> library
are
<CODE>alldifferent/1</CODE>, <CODE>maxlist/2</CODE>, <CODE>occurrences/3</CODE> and
<CODE>sorted/2</CODE>.
For more details see section <A HREF="tutorial058.html#secglobal">8.5</A> in chapter <A HREF="tutorial053.html#chapicintro">8</A>.<BR>
<BR>
<A NAME="toc53"></A>
<H3 CLASS="subsection"><A NAME="htoc100">7.2.4</A>&nbsp;&nbsp;Scheduling Constraints: <EM>ic_cumulative, ic_edge_finder</EM></H3>
<A NAME="@default170"></A>
<A NAME="@default171"></A>
<A NAME="shortsecsched"></A>
There are several  ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> libraries implementing global constraints for
scheduling applications.
The constraints take a list
of tasks (start times, durations and resource needs), and a maximum
resource level. They reduce the finite domains of the task start times
by reasoning on resource bottlenecks [<A HREF="tutorial133.html#lepape"><CITE>13</CITE></A>]. Three  ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> libraries
implementing scheduling constraints are
<EM>ic_cumulative</EM>, <EM>ic_edge_finder</EM> and <EM>ic_edge_finder3</EM>.
They implement the same constraints declaratively, but with
different time complexity and strength of propagation.
For more details see the library documentation in the Reference Manual.<BR>
<BR>
<A NAME="toc54"></A>
<H3 CLASS="subsection"><A NAME="htoc101">7.2.5</A>&nbsp;&nbsp;Finite Integer Sets: <EM>ic_sets</EM></H3>
<A NAME="@default172"></A>
<A NAME="shortsecsets"></A>
The <EM>ic_sets</EM> library
implements constraints over the domain of finite
sets of integers<SUP><A NAME="text2" HREF="tutorial046.html#note2">2</A></SUP>.
The constraints are the usual relations over sets,
e.g. membership, inclusion, intersection, union, disjointness.
In addition, there are constraints between sets and integers, e.g.
cardinality and weight constraints. For those, the <EM>ic_sets</EM> library
cooperates with the <EM>ic</EM> library.
For more details see chapter <A HREF="tutorial070.html#icsets">10</A>.<BR>
<BR>
<A NAME="toc55"></A>
<H3 CLASS="subsection"><A NAME="htoc102">7.2.6</A>&nbsp;&nbsp;Linear Constraints: <EM>eplex</EM></H3>
<A NAME="@default173"></A>
<A NAME="shortseceplex"></A>
<EM>eplex</EM> supports a tight integration [<A HREF="tutorial133.html#Bockmayr"><CITE>4</CITE></A>] between an
external linear programming (LP) / mixed integer programming (MIP)
solver (XPRESS [<A HREF="tutorial133.html#Dash"><CITE>20</CITE></A>] or CPLEX [<A HREF="tutorial133.html#ILOG"><CITE>11</CITE></A>]) and  ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>. 
Constraints as well as variables can be handled by the external LP/MIP
solver, by a propagation solver like <EM>ic</EM>, or by both.
Optimal solutions and other solution porperties can be returned to
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> as required.
Search can be carried out either in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> or in the external solver.
For more details see chapter <A HREF="tutorial115.html#chapeplex">16</A>.<BR>
<BR>
<A NAME="toc56"></A>
<H3 CLASS="subsection"><A NAME="htoc103">7.2.7</A>&nbsp;&nbsp;Constraints over symbols: <EM>ic_symbolic</EM></H3>
<A NAME="@default174"></A>
<A NAME="shortsecsymbolic"></A>
The <EM>ic_symbolic</EM> library supports variables ranging over ordered
symbolic domains (e.g. the names of products, the names of the weekdays),
and constraints over such variables. It is implemented by mapping such
variables and constraints to variables over integers and <EM>ic</EM>-constraints.<BR>
<BR>
<HR>
<A HREF="tutorial047.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial046.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial049.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
